// https://leetcode.cn/problems/maximum-score-after-splitting-a-string/
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxScore(string s) {
		int len = s.size();
		int dpl[len - 1];
		int dpr[len - 1];
		dpl[0] = s[0] == '1' ? 0 : 1;
		dpr[0] = s[len - 1] == '1' ? 1 : 0;
		for(int i = 1; i < len-1; i++){
			if(s[i] == '0'){
				dpl[i] = dpl[i-1]+1;
			}else{
				dpl[i] = dpl[i-1];
			}
			
			if(s[len - 1 - i] == '1'){
				dpr[i] = dpr[i-1] + 1;
			}else{
				dpr[i] = dpr[i-1];
			}
		}
		int maxN = 0;
		for(int i = 0; i < len - 1; i++){
			maxN = max(maxN, dpl[i] + dpr[len - 2 - i]);
		}
		
		return maxN;
    }
};

int main(){
	Solution so;
	cout << so.maxScore("011101") << endl;
	return 0;
}